package formal.tree.bst;

/**
 * 将有序数组转换为二叉搜索树
 * @author DengYuan2
 * @create 2021-01-24 20:34
 */
public class E_108 {
    public static void main(String[] args) {
//        int[] a = {-10,-3,0,5,9};
//        int[] a = {1,2,3,4,5,6,7,8,9};
        int[] a = {};
        TreeNode res = sortedArrayToBST(a);
        System.out.println(res);
    }

    /**
     *  1 2 3 4    5     6 7 8 9
                        5
                  2           7
                1   3        6  8
                      4          9

     * 我的写法-不断取中间，左边的中间放在左节点，右边的中间放在右节点
     * 有点麻烦
     * @param nums
     * @return
     */
    public static TreeNode sortedArrayToBST(int[] nums) {
        int length = nums.length;
        if (length==0){
            return null;
        }
        int mid = (length-1)/2;
        TreeNode root = new TreeNode(nums[mid]);
        midMethod(nums,root,0,mid,length-1);
        return root;
    }
    //0 4 8
    public static void midMethod(int[] nums,TreeNode root,int left,int mid,int right){
        if (root==null){
            return;
        }
        root.left = helper(nums,left,mid-1);
        root.right = helper(nums,mid+1,right);
        midMethod(nums,root.left,left,(left+mid-1)/2,mid-1);
        midMethod(nums,root.right,mid+1,(mid+1+right)/2,right);
    }

    /**
     * 返回中间节点
     * @param nums
     * @param left
     * @param right
     * @return
     */
    public static TreeNode helper(int[] nums,int left,int right){
        TreeNode node = null;
        if (left<=right){
            int mid = (left+right)/2;
            node = new TreeNode(nums[mid]);
        }
        return node;
    }

    /**
     * 大神的写法-思路相似-写法超简单啊
     * @param nums
     * @return
     */
    public static TreeNode sortedArrayToBST2(int[] nums) {
        return toBST(nums,0,nums.length-1);
    }

    public static TreeNode toBST(int[] nums,int left,int right){
        TreeNode node = null;
        if (left<=right){
            int mid = (left+right)/2;
            node=new TreeNode(nums[mid]);
            node.left=toBST(nums,left,mid-1);
            node.right=toBST(nums,mid+1,right);
        }
        return node;
    }
}
